#region MIT License

/*
 * Copyright (c) 2009-2010 Nick Gravelyn (nick@gravelyn.com), Markus Ewald (cygon@nuclex.org)
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a 
 * copy of this software and associated documentation files (the "Software"), 
 * to deal in the Software without restriction, including without limitation 
 * the rights to use, copy, modify, merge, publish, distribute, sublicense, 
 * and/or sell copies of the Software, and to permit persons to whom the Software 
 * is furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all 
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, 
 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A 
 * PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT 
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 
 * 
 */

#endregion

using System;
using System.Collections.Generic;
using System.Drawing.Imaging;
using Microsoft.Xna.Framework;

namespace AnimationPackerEngine.Packing
{
    public class ImagePacker
    {
        // various properties of the resulting image
        private bool mRequirePow2;
        private bool mRequireSquare;
        private int mPadding;
        private int mOutputWidth;
        private int mOutputHeight;

        // some dictionaries to hold the image sizes and destination rectangles
        private List<ProcessingFrame> mFrames = new List<ProcessingFrame>();

        // progress display
        private IPackingProgressDisplay mProgressDisplay;

        public ImagePacker(IPackingProgressDisplay progressDisplay)
        {
            mProgressDisplay = progressDisplay;
        }

        public bool PackImage(ProcessParams compileParams, List<ProcessingAnimation> animations, out System.Drawing.Bitmap outputImage, IPackingStatus status)
        {
            mRequirePow2 = compileParams.Pow2;
            mRequireSquare = compileParams.Square;
            mOutputWidth = compileParams.MaxWidth;
            mOutputHeight = compileParams.MaxHeight;
            mPadding = compileParams.Padding;

            outputImage = null;

            // make sure our dictionaries are cleared before starting
            mFrames.Clear();

            foreach (var animation in animations)
            {
                foreach (var frame in animation.Frames)
                {
                    mFrames.Add(frame);
                }
            }

            // sort our files by file size so we place large sprites first
            mFrames.Sort();

            // try to pack the images
            if (!PackImageRectangles())
            {
                status.Error("Failed to pack all sprites into output image.");
                return false;
            }

            // make our output image
            try
            {
                outputImage = CreateOutputImage();
            }
            catch (Exception e)
            {
                status.FatalException("Failed to save sprite atlas image", e);
                return false;
            }

            // go through our image placements and replace the width/height found in there with
            // each image's actual width/height (since the ones in imagePlacement will have padding)
            foreach (var animation in animations)
            {
                for (int i = 0; i != animation.Frames.Count; ++i)
                {
                    System.Drawing.Size s = animation.Frames[i].Size;
                    Rectangle r = animation.Frames[i].AtlasRect;

                    r.Width = s.Width;
                    r.Height = s.Height;

                    animation.Frames[i].AtlasRect = r;
                }
            }

            // clear our dictionary just to free up some memory
            mFrames.Clear();

            return true;
        }

        // This method does some trickery type stuff where we perform the TestPackingImages method over and over, 
        // trying to reduce the image size until we have found the smallest possible image we can fit.
        private bool PackImageRectangles()
        {
            // get the size of our smallest image
            int smallestWidth = int.MaxValue;
            int smallestHeight = int.MaxValue;
            foreach (var frame in mFrames)
            {
                smallestWidth = Math.Min(smallestWidth, frame.Size.Width);
                smallestHeight = Math.Min(smallestHeight, frame.Size.Height);
            }

            // we need a couple values for testing
            int testWidth = mOutputWidth;
            int testHeight = mOutputHeight;

            bool shrinkVertical = false;

            int packAttempt = 0;

            // just keep looping...
            while (true)
            {
                mProgressDisplay.ProgressSectionName(string.Format("Packing (attempt {0})", ++packAttempt));
                mProgressDisplay.ResetProgress(mFrames.Count);

                // try to pack the images into our current test size
                if (!TestPackingImages(testWidth, testHeight))
                {
                    // if that failed...

                    // if we're on packAttempt 1, then we've never succeeded at TestPackingImages
                    // so return false since there's no way to fit the images into our max size texture
                    if (packAttempt == 1)
                    {
                        return false;
                    }

                    // otherwise return true to use our last good results
                    if (shrinkVertical)
                    {
                        return true;
                    }

                    shrinkVertical = true;
                    testWidth += smallestWidth + mPadding + mPadding;
                    testHeight += smallestHeight + mPadding + mPadding;
                    continue;
                }

                // figure out the smallest bitmap that will hold all the images
                testWidth = testHeight = 0;
                foreach (var frame in mFrames)
                {
                    testWidth = Math.Max(testWidth, frame.AtlasRect.Right);
                    testHeight = Math.Max(testHeight, frame.AtlasRect.Bottom);
                }

                // subtract the extra padding on the right and bottom
                if (!shrinkVertical)
                {
                    testWidth -= mPadding;
                }

                testHeight -= mPadding;

                // if we require a power of two texture, find the next power of two that can fit this image
                if (mRequirePow2)
                {
                    testWidth = MiscHelper.FindNextPowerOfTwo(testWidth);
                    testHeight = MiscHelper.FindNextPowerOfTwo(testHeight);
                }

                // if we require a square texture, set the width and height to the larger of the two
                if (mRequireSquare)
                {
                    int max = Math.Max(testWidth, testHeight);
                    testWidth = testHeight = max;
                }

                // if the test results are the same as our last output results, we've reached an optimal size,
                // so we can just be done
                if (testWidth == mOutputWidth && testHeight == mOutputHeight)
                {
                    if (shrinkVertical)
                    {
                        return true;
                    }

                    shrinkVertical = true;
                }

                // save the test results as our last known good results
                mOutputWidth = testWidth;
                mOutputHeight = testHeight;

                // subtract the smallest image size out for the next test iteration
                if (!shrinkVertical)
                {
                    testWidth -= smallestWidth;
                }

                testHeight -= smallestHeight;
            }
        }

        private bool TestPackingImages(int testWidth, int testHeight)
        {
            // create the rectangle packer
            ArevaloRectanglePacker rectanglePacker = new ArevaloRectanglePacker(testWidth, testHeight);

            for (int i = 0; i != mFrames.Count; ++i)
            {
                // get the bitmap for this file
                System.Drawing.Size size = mFrames[i].Size;
                size.Width += mPadding;
                size.Height += mPadding;

                // pack the image
                System.Drawing.Point origin;
                if (!rectanglePacker.TryPack(size.Width, size.Height, out origin))
                {
                    return false;
                }

                // add the destination rectangle to our dictionary
                mFrames[i].AtlasRect = new Rectangle(origin.X, origin.Y, size.Width, size.Height);

                mProgressDisplay.Update(1);
            }

            return true;
        }

        private System.Drawing.Bitmap CreateOutputImage()
        {
            mProgressDisplay.ProgressSectionName("Creating final output image...");
            mProgressDisplay.ResetProgress(mFrames.Count);

            System.Drawing.Bitmap outputImage = new System.Drawing.Bitmap(mOutputWidth, mOutputHeight, PixelFormat.Format32bppArgb);

            // draw all the images into the output image
            foreach (var frame in mFrames)
            {
                // TODO: !!! use Bitmap.LockBits instead of SetPixel

                // copy pixels over to avoid antialiasing or any other side effects of drawing
                // the subimages to the output image using Graphics
                for (int x = 0; x < frame.Bitmap.Width; x++)
                {
                    for (int y = 0; y < frame.Bitmap.Height; y++)
                    {
                        outputImage.SetPixel(frame.AtlasRect.X + x, frame.AtlasRect.Y + y, frame.Bitmap.GetPixel(x, y));
                    }
                }

                mProgressDisplay.Update(1);
            }

            mProgressDisplay.ProgressComplete();

            return outputImage;
        }
    }
}